/**
 * 使用堆来模拟优先队列
 */

function PriorityList(comp) {
    this.arr = [];
    this.length = 0;
    this.comp = comp;
}
//放进去，自动根据优先级排列
PriorityList.prototype.push = function (x) {
    this.arr.unshift(x);
    this.length++;
    heapMinAdjust(this.arr, 0, this.length);
}

//将优先级最高的取出来，取出来后优先级最高的放在最前面
PriorityList.prototype.pop = function () {
    if (this.length === 0) return undefined;
    let temp = this.arr.shift();
    this.length--;
    heapMinAdjust(this.arr, 0, this.length);
    return temp;
}
//将最优先的展示出来
PriorityList.prototype.top = function () {
    if (this.length === 0) return undefined;
    return this.arr[0];
}

function heapAdjust(arr,index,len){
    while(2*index+1 < len){
        let cur = 2 * index + 1;
        if (cur + 1 < len) cur = comp(arr[cur+1],arr[cur]) >= 0 ? cur + 1 : cur;
        if (comp(arr[index],arr[cur]) < 0) {
            [arr[index], arr[cur]] = [arr[cur], arr[index]];
            index = cur;
        } else break;
    }
}



//建立大顶堆
function maxheapSet(arr) {
    //自低向上
    let len = arr.length;
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapMaxAdjust(arr, i, len);
    }
}

//大顶堆调整
function heapMaxAdjust(arr, index, len) {
    while (2 * index + 1 < len) {
        let cur = 2 * index + 1;
        if (cur + 1 < len) cur = arr[cur + 1] > arr[cur] ? cur + 1 : cur;
        if (arr[index] < arr[cur]) {
            [arr[index], arr[cur]] = [arr[cur], arr[index]];
            index = cur;
        } else break;
    }
}

//小顶堆建立
function minheapSet(arr) {
    let len = arr.length;
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapMinAdjust(arr, i, len)
    }
}

function heapMinAdjust(arr, index, len) {
    while (2 * index + 1 < len) {
        let cur = 2 * index + 1;
        if (cur + 1 < len) cur = arr[cur + 1] < arr[cur] ? cur + 1 : cur;
        if (arr[index] > arr[cur]) {
            [arr[index], arr[cur]] = [arr[cur], arr[index]];
            index = cur;
        } else break;
    }
}



// // let arr = [2,4,6,8,3];
// // maxheapSet(arr);
// // arr.splice(0,1);
// // heapMaxAdjust(arr,0,arr.length);
// // arr.splice(0,1);
// // heapMaxAdjust(arr,0,arr.length);
// // arr.splice(0,1);
// // heapMaxAdjust(arr,0,arr.length);

// let arr1 = [3,5,6,2,1,9,7];
// minheapSet(arr1);
// arr1.splice(0,1);
// arr1.splice(0,1);
// heapMinAdjust(arr1,0,arr1.length)
// // console.log(arr[0]);
// console.log(arr1[0])


let plist = new PriorityList();
plist.push(3);
plist.push(2);
plist.push(4);
plist.push(6);plist.push(100);
plist.push(1);
plist.pop();
plist.pop();
console.log(plist.pop());
console.log(plist.top())
